Transportation planning by a shipper (who owns and/or controls freight) involves determining publicly-available means of moving the freight (also called cargo) from its origin to its destination through a number of strategies, such as consolidation of shipments, continuous moves of vehicles, as well as selection of carriers and modes (air, ground, sea). Reduction of cost is typically the predominant objective of a shipper in selecting specific means of transportation, although other business and service objectives may also be important considerations. Shipments (also known as transportation orders, shipment orders, delivery orders, or simply orders) are movements of freight and constitute the basic element of transportation planning.
Starting with orders for movement of freight (i.e. shipments), one element of transportation planning involves the shipper manually and/or automatically creating groups of shipments that can be moved together in a single vehicle (such as a truck or trailer), in a process known as load building or load consolidation. Specifically, load consolidation involves the shipper combining shipments of small sizes that otherwise would be sent by Less than TruckLoad (LTL) services or parcel (also known as small package) services into larger shipments that can be sent by Truckload services (also called “carriers”) that operate wheeled vehicles on public highways. If well utilized full truckload shipments can be created, cost savings are achieved since the per unit costs of sending large shipments by Truckload service are usually less expensive than the per unit costs of sending small shipments by LTL or Parcel service. This only holds if the capacity of a truck or trailer is well utilized because the charges for a truckload movement generally vary only with the distance travelled, regardless of the amount of load in the truck. LTL and parcel charges, on the other hand, vary both with the size of the shipment and the distance covered. Truckload services are provided by, for example, J. B. Hunt, Schneider National and Werner Enterprises. LTL services are provided by, for example, Yellow Freight and Roadway Express. Parcel services are provided by, for example, UPS, FedEx and DHL.
One of the load consolidation strategies used by human transportation planners either manually or by using transportation planning systems is to group multiple small shipments into a truckload. Specifically, as shown in FIG. 1A, pooling (or hubbing or zone skipping) can involve bringing small shipments together at a consolidation center so that they can continue movement on a truckload service—instead of sending them all the way (point-to-point) by less-than-truckload (LTL) or parcel services which are higher priced. As further shown in FIG. 1B, this can also work in the other direction, breaking up a truckload from a single origin at a deconsolidation center for further transportation by LTL or parcel services. Finally, as shown in FIG. 1C a shipper can put both of these together using a truckload line haul between cross-docking (or pooling) facilities, with the remainder of the distance covered by LTL services or parcel services.
Another strategy used by a shipper for combining small shipments into truckloads is to have a single truck make multiple pickup and/or dropoff stops. These truckloads are called “multi-stop” truckloads and entail missions that pick up goods and/or drop them off in more than one location. FIG. 1D illustrates a combined multi-stop and pooling mission, in which a truck makes several pickups and then several dropoffs, one of which is at a deconsolidation center from where several orders continue to final delivery via LTL or parcel services. The cost of the mission is computed by a truckload service (also called “carrier”) based on the distance traveled by the truck (applied as a per mile charge) as well as limited additional costs, including costs for each extra stop incurred on the route from the origin to the destination.
When executing a multi-stop truckload, the truck moves less than fully loaded for some part of its path between the first origin and the last destination, as illustrated in FIG. 1E. In this illustration, a single truck picks up three shipments bound for stops W, X, and Y at origin stop A. At stop B, the truck picks up another shipment traveling to stop W. The truck then proceeds to stop W. The truck drops the shipments from stops A and B that were bound for W at this stop. The truck proceeds with the remaining shipments picked up from A, bound for stops X and Y. At stop C, the truck picks up another shipment bound for stop Z. At stop X, the truck drops off the shipment picked up from A that was bound for X. The truck proceeds with the remaining shipments to stop D, where it picks up another shipment bound for stop Y. At stop Y, the truck drops off the two shipments, one from A and the other from D, which were bound for Y. The truck then proceeds to stop Z where it drops off the shipment picked up from C that was bound for Z.
Despite being underutilized in certain portions of a mission, e.g. between stops Y and Z in FIG. 1E, such multi-stop truckloads can provide a shipper with great economies versus LTL/parcel movement—the more so as a truck's overall utilization (averaged across the entire path) rises, and as the deviation from a geographically direct route between the first origination and the last destination decreases. Note that some carriers permit interspersing of loading and unloading stops as shown in FIG. 1E; other carriers require that all loading stops occur before the first unloading stop as shown in FIG. 1D.
The effective volume available in a truck or trailer is usually less than its physical volume, because shipments are not all of perfect sizes and shapes to fit exactly into the physical volume of the truck or trailer. For example, consider a standard 53′ long×102″ wide trailer (having a nose height of 110″ and rear height of 112″). Assume that its physical volume is about 4,130 cubic feet. When loading this trailer, it is difficult (if not impossible) to fill it with 4,130 cubic feet of cargo (to “square out” the trailer). This is due to the irregularly varying sizes and shapes of the pieces of cargo as well as the need to leave room around the cargo to allow it to be inserted into and removed from the vehicle. Realistically, when using prior art transportation planning software to do load consolidation, a human transportation planner may set a single limit on the volume of cargo that can be fit practically in each type of vehicle. For example, the human operator may specify the maximum cargo that can be fit as follows: 2,850 cubic feet in a standard 53′×102″ trailer, and 2,300 cubic feet in a standard 48′×102″ trailer.
Most prior art transportation planning software (known to the present inventors) treats these operator-set limits as hard constraints—the prior art software won't build a truckload that exceeds these limits by even 1 cubic foot. In the above-described example, the prior art software may produce one trip and one shipment as follows: (1) a trip for a truckload of 2000 cubic feet which underutilizes the standard 53′×102″ trailer and (2) a less-than truckload (LTL) shipment of 851 cubic feet which is expensive. Thus, the prior art software fails to capture savings from combination of orders in trip (1) and shipment (2), even when such savings are large and the risk that 2,851 cubic feet of cargo will actually not fit into the standard 53′×102″ trailer (with its 4,130 cubic feet of interior space) is small.
All trips are presented to the transportation planner as items in a large transportation plan generated by the prior art software, it is very difficult and time consuming to manually go through the plan and detect such truckload combinations that are economical but that were not produced by the software. In the above described example, a transportation planner would have to manually detect that combining trip (1) and shipment (2) would barely exceed the operator-set limit by only 1 cubic foot.
Even assuming a detection feature exists in some prior art software that brings such combinations to the human operator's attention, a typical transportation plan that produces 300 multi-stop trips may have up to 30% of the truckloads (i.e. 90 truckloads) that need to be manually reviewed and reworked. If a human transportation planner spends just 5 minutes working on each truckload, that amounts to 7.5 hours or a full business day! Such amount of time spent in repairing existing truckloads negates the time savings from doing transportation planning automatically in the first place.
US Patent Application 2004/0107110 filed by Jens Gottlieb et al., published Jun. 3, 2004, entitled “Optimization of transport with multiple vehicles” is hereby incorporated by reference herein in its entirety. The reader is requested to review this patent application in detail. Briefly, this patent application describes optimizing a total cost associated with transporting products on a set of vehicles. Orders representing products are assigned to one or more vehicles in the set. The assignment defines a sequence of pickup and delivery activities for the vehicles. One or more orders are deleted from one or more vehicles; at least one order from the deleted orders is inserted into a vehicle; the assignment is changed for at least one vehicle; and a cost is determined for the transportation of the products on the set of vehicles. The steps of deleting one or more orders, inserting at least one order, changing the assignment, and determining a cost, are repeated until an optimal cost has been determined.
US Patent Application 2004/0107110 also discusses vehicle limitations that specify restrictions on using a vehicle for transportation. For example, the vehicle can be used on a limited route or schedule. Examples of such vehicles include fixed-trip vehicles, such as trains or ships, that operate on predefined routes according to strict schedules. Alternatively, such vehicles can be large trucks that cannot travel but on certain roads. The vehicle can have driving limits specifying a maximum time, distance, or intermediate stops for a single trip.
US Patent Application 2004/0107110 also states that vehicle limitations can further include loading capacities, that is, limitations on the amount of goods that can be loaded into a vehicle. The loading capacities can include weight, volume, or pallet limitations, or any other limitations in arbitrary dimensions and units. The vehicle limitations can also include restrictions on the types of goods the vehicle can transport. Also, a fixed-trip vehicle can have a loading capacity calendar that characterizes the loading capacity as a function of the time. For example, a train or a ship can have different restrictions on the loading capacity at different locations or at different times. Note that this method pertains to one particular variant of the transportation planning problem commonly known as the “Fleet Routing Problem” or “Vehicle Scheduling Problem” or “Vehicle Routing and Scheduling Problem” wherein the transportation orders are to be assigned to a known finite set of vehicles (e.g. 35 trucks owned by a furniture seller).
For additional patent prior art, see U.S. Pat. No. 5,758,329 granted to Wojcik et al. on May 26, 1998, and entitled “System for Managing Customer Orders and Method of Implementation” that is incorporated by reference herein its entirety. In particular FIG. 13 and the related description from the bottom of column 8 to the top of column 10 of this patent refers to different weights of different commodities being able to fit in the same trailer but this is the result of goods of different densities (juice and meat) being constrained by the same volume or “cube” limitation. A particular volume of meat weighs more than the same volume of juice and hence a greater weight of meat can be accommodated in the trailer, until the maximum limit on truckload volume (cube) is exceeded.
See also US Patent Application 2002/0019759 by Arunapuram, Sundararajan et al. published Feb. 14, 2002 and entitled “Transportation planning, execution, and freight payments managers and related methods.” which is hereby incorporated by reference herein in its entirety.
Numerous articles have been written and published on transportation planning. For general background, see an article entitled “Joe's Juggling Act,” OR/MS Today, December 1998.